'''
给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

如果无法这么操作，就请返回原数组。

 

示例 1：

输入：arr = [3,2,1]
输出：[3,1,2]
解释：交换 2 和 1
示例 2：

输入：arr = [1,1,5]
输出：[1,1,5]
解释：已经是最小排列
示例 3：

输入：arr = [1,9,4,6,7]
输出：[1,7,4,6,9]
解释：交换 9 和 7

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/previous-permutation-with-one-swap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def prevPermOpt1(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        n = len(arr)
        ##############思路：升序的区段是暂且不用变的，因为是小于原先排序 的 最大排列

        #### 从右往左，第一个逆序的位置
        L = n - 2
        while -1 < L and arr[L] <= arr[L + 1]:
            L -= 1
        if L == -1:  # 超界了，整个数组，都是升序的。
            return arr

        #### 寻找L右边，第一个大于A[i]的R。（贪心，如果 1 1 1 要置换成3，肯定置换前面的）
        R = L + 1
        R_first_max_id = R  # 最大值的第一个（重复情况的第一个！第一个！！第一个！！！）

        while R < n and arr[L] > arr[R]:
            if arr[R] > arr[R_first_max_id]:
                R_first_max_id = R
                print(R)
            R += 1
        R -= 1

        #### 交换
        if arr[L] > arr[R_first_max_id]:
            arr[L], arr[R_first_max_id] = arr[R_first_max_id], arr[L]
        return arr

arr = [3,2,1]
Solution().prevPermOpt1(arr)